{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Count Substrings Without Repeating Character"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #hash-table #string #sliding-window"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #哈希表 #字符串 #滑动窗口"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: numberOfSpecialSubstrings"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #计算没有重复字符的子字符串数量"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定你一个只包含小写英文字母的字符串 <code>s</code> 。如果一个子字符串不包含任何字符至少出现两次（换句话说，它不包含重复字符），则称其为 <strong>特殊</strong> 子字符串。你的任务是计算 <strong>特殊</strong> 子字符串的数量。例如，在字符串 <code>\"pop\"</code> 中，子串 <code>\"po\"</code> 是一个特殊子字符串，然而 <code>\"pop\"</code> 不是 <strong>特殊</strong> 子字符串（因为 <code>'p'</code> 出现了两次）。</p>\n",
    "\n",
    "<p>返回 <strong>特殊</strong> 子字符串的数量。</p>\n",
    "\n",
    "<p><strong>子字符串</strong> 是指字符串中连续的字符序列。例如，<code>\"abc\"</code> 是 <code>\"abcd\"</code> 的一个子字符串，但 <code>\"acd\"</code> 不是。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong class=\"example\">示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>s = \"abcd\"\n",
    "<b>输出：</b>10\n",
    "<b>解释：</b>由于每个字符只出现一次，每个子串都是特殊子串。长度为 1 的子串有 4 个，长度为 2 的有 3 个，长度为 3 的有 2 个，长度为 4 的有 1 个。所以一共有 4 + 3 + 2 + 1 = 10 个特殊子串。\n",
    "</pre>\n",
    "\n",
    "<p><strong class=\"example\">示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>s = \"ooo\"\n",
    "<b>输出：</b>3\n",
    "<b>解释：</b>任何长度至少为 2 的子串都包含重复字符。所以我们要计算长度为 1 的子串的数量，即 3 个。\n",
    "</pre>\n",
    "\n",
    "<p><strong class=\"example\">示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>s = \"abab\"\n",
    "<b>输出：</b>7\n",
    "<b>解释：</b>特殊子串如下（按起始位置排序）： \n",
    "长度为 1 的特殊子串：\"a\", \"b\", \"a\", \"b\" \n",
    "长度为 2 的特殊子串：\"ab\", \"ba\", \"ab\" \n",
    "并且可以证明没有长度至少为 3 的特殊子串。所以答案是4 + 3 = 7。</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= s.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>s</code> 只包含小写英文字母。</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [count-substrings-without-repeating-character](https://leetcode.cn/problems/count-substrings-without-repeating-character/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [count-substrings-without-repeating-character](https://leetcode.cn/problems/count-substrings-without-repeating-character/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"abcd\"', '\"ooo\"', '\"abab\"']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfSpecialSubstrings(self, s: str) -> int:\n",
    "      clst={}\n",
    "      res=0\n",
    "      l=-1\n",
    "      for i,t in enumerate(s):\n",
    "        if t in clst:\n",
    "          l=max(l,clst[t])\n",
    "        res+=i-l\n",
    "        clst[t]=i\n",
    "      return res\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # # 滑动窗口\n",
    "    def numberOfSpecialSubstrings(self, s: str) -> int:\n",
    "        has, res, j = set(), 0, 0\n",
    "        for i, v in enumerate(s):\n",
    "            while v in has:\n",
    "                has.remove(s[j])\n",
    "                j += 1\n",
    "\n",
    "            has.add(v)\n",
    "            res += i - j + 1\n",
    "\n",
    "        return res\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfSpecialSubstrings(self, s: str) -> int:\n",
    "        result, j, d = 0, 0, {}\n",
    "        for i, c in enumerate(s):\n",
    "            if c in d:\n",
    "                j = max(j, d[c] + 1)\n",
    "            result += i - j + 1\n",
    "            d[c] = i\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfSpecialSubstrings(self, s: str) -> int:\n",
    "        d = dict()\n",
    "        l = 0\n",
    "        ret = 0\n",
    "        for r, c in enumerate(s):\n",
    "            if c in d and d[c] >= l:\n",
    "                l = d[c] + 1\n",
    "            ret += r - l + 1\n",
    "            d[c] = r\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfSpecialSubstrings(self, s: str) -> int:\n",
    "        ss, res, srt = set(), 0, 0\n",
    "        for i, v in enumerate(s):\n",
    "            while v in ss:\n",
    "                ss.remove(s[srt])\n",
    "                srt += 1\n",
    "            ss.add(v)\n",
    "            res += i - srt + 1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfSpecialSubstrings(self, s: str) -> int:\n",
    "        d = Counter()\n",
    "        l, res = 0, 0\n",
    "        for r, c in enumerate(s):\n",
    "            d[c] += 1\n",
    "            while d[c] > 1:\n",
    "                d[s[l]] -= 1\n",
    "                l += 1\n",
    "            res += r - l + 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfSpecialSubstrings(self, s: str) -> int:\n",
    "        has, res, j = set(), 0, 0\n",
    "        for i, v in enumerate(s):\n",
    "            while v in has:\n",
    "                has.remove(s[j])\n",
    "                j += 1\n",
    "\n",
    "            has.add(v)\n",
    "            res += i - j + 1\n",
    "\n",
    "        return res\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfSpecialSubstrings(self, s: str) -> int:\n",
    "        if not s:\n",
    "            return 0\n",
    "        dictionary = collections.defaultdict(int)\n",
    "        dictionary[s[0]] += 1\n",
    "\n",
    "        i, n = 0, len(s)\n",
    "        res = 1\n",
    "\n",
    "        for j in range(1, n):\n",
    "            dictionary[s[j]] += 1\n",
    "            while dictionary[s[j]] > 1:\n",
    "                dictionary[s[i]] -= 1\n",
    "                i += 1\n",
    "\n",
    "            res += j-i+1\n",
    "\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfSpecialSubstrings(self, s: str) -> int:\n",
    "        ans,n,j=0,len(s),0\n",
    "        d=defaultdict(int)\n",
    "        for i in range(n):\n",
    "            d[s[i]]+=1\n",
    "            while d[s[i]]>1:\n",
    "                d[s[j]]-=1\n",
    "                j+=1\n",
    "            ans+=i-j+1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfSpecialSubstrings(self, s: str) -> int:\n",
    "        ss, res, srt = set(), 0, 0\n",
    "        for i, v in enumerate(s):\n",
    "            while v in ss:\n",
    "                ss.remove(s[srt])\n",
    "                srt += 1\n",
    "            ss.add(v)\n",
    "            res += i - srt + 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfSpecialSubstrings(self, s: str) -> int:\n",
    "        length = len(s)\n",
    "        count = 0\n",
    "\n",
    "        for i in range(length):\n",
    "            j = i\n",
    "            seen = set()\n",
    "            while j < length and s[j] not in seen:\n",
    "                seen.add(s[j])\n",
    "                count += 1\n",
    "                j += 1\n",
    "\n",
    "        return count\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfSpecialSubstrings(self, s: str) -> int:\n",
    "        ans = left = 0\n",
    "        window = set()\n",
    "        for right, c in enumerate(s):\n",
    "            while c in window:\n",
    "                window.remove(s[left])\n",
    "                left += 1\n",
    "            window.add(c)\n",
    "            ans += right - left + 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfSpecialSubstrings(self, s: str) -> int:\n",
    "        seen = set()\n",
    "        n = len(s)\n",
    "        ans = l = 0\n",
    "        for r in range(n):\n",
    "            if s[r] not in seen:    \n",
    "                ans += r - l + 1\n",
    "                seen.add(s[r])\n",
    "            else:\n",
    "                while s[l] != s[r]:\n",
    "                    seen.remove(s[l])\n",
    "                    l += 1\n",
    "                l += 1\n",
    "                ans += r - l + 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfSpecialSubstrings(self, s: str) -> int:\n",
    "        ans = 0\n",
    "        n = len(s)\n",
    "\n",
    "        left = 0\n",
    "        right = 1\n",
    "        count = [0 for i in range(26)]\n",
    "        count[ord(s[left]) - ord('a')] += 1\n",
    "        while left < n:\n",
    "            while right < n and count[ord(s[right]) - ord('a')] + 1 < 2:\n",
    "                count[ord(s[right]) - ord('a')] += 1\n",
    "                right += 1\n",
    "            if all(a <= 1 for a in count):\n",
    "                ans += right - left\n",
    "            count[ord(s[left]) - ord('a')] -= 1\n",
    "            left += 1\n",
    "        return ans \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfSpecialSubstrings(self, s: str) -> int:\n",
    "        res, pre = 0, -1\n",
    "        last = defaultdict(lambda: -1)\n",
    "        for i, ch in enumerate(s):\n",
    "            # pre = left = max(pre, last[ch])\n",
    "            pre = left = pre if pre > last[ch] else last[ch]\n",
    "            res += i - left\n",
    "            last[ch] = i\n",
    "        return res\n",
    "            "
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
